package com.sicheng.lc.lc笔试.字节篇;

import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/8/28 11:01
 */
public class 翻转子数组后的最大子段和 {
    static long MIN = -(Long.MAX_VALUE >> 20);

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }

        // 以k结尾的最大字段和 + 后半段的最大后缀和
        // 多余的部分可以认为通过翻转被删掉
        //  nums[0~k~n-1]
        //  0 1 2 ... l...k....r r+1 ..... n-1
        //   k+1~r可以认为被删除了 r+1~n-1重新续上sum[k]
        // dp[j]表示从右开始的最大后缀和

        // 复杂度分析
        // 找前半段是的字段和 O(N) + 后半段以O(1)找到最大后缀
        // 总复杂度O(N)
        long[] dp = new long[n + 1];
        long sum = 0, max = MIN;
        dp[n] = MIN;
        for (int j = n - 1; j >= 0; j--) {
            sum += nums[j];
            dp[j] = Math.max(sum, dp[j + 1]);
        }
        sum = 0;
        long res = MIN;
        dp[n] = 0;
        for (int i = 0; i < n; i++) {
            if (sum + nums[i] < nums[i]) {
                sum = 0;
            }
            sum += nums[i];
            max = Math.max(max, sum);
            res = Math.max(res, max + dp[i + 1]);
        }
        System.out.println(res);

    }
}
